package arrAndstr;
/*
    11. 盛最多水的容器
    这题最有的做法是双指针：假设i<j
        如果height[i] <= height[j] --> i++
        否则 --> j--
    可行性证明：（类似于桶装水，能装多少取决于最短的木头
        第一种情况：右边的指针无论怎么走，都不会让结果更大了
        第二种情况：左边的指针无论怎么走，都不会让结果更大了
 */
public class T11 {

    public static void main(String[] args) {
        int[] array = new int[]{1,8,6,2,5,4,8,3,7};
        System.out.println(maxArea(array));
    }

    public static int maxArea(int[] height) {
        int len = height.length;
        int heightest = 0;
        int result = 0;

        // 我这里是一个剪枝操作，但是只意识到了一边，没想到怎么处理另一边
        for(int i=0; i<len-1; i++) {
            int heightNow = height[i];
            if(heightNow <= heightest) {
                continue;
            } else {
                heightest = heightNow;
            }
            int resultTemp = findMaxHeight(height, i);
            result = result > resultTemp ? result : resultTemp;
        }

        return result;
    }

    public static int findMaxHeight(int[] height, int startIndex) {
        int startHeight = height[startIndex];
        int len = height.length;
        int valueMax = 0;

        for(int i=startIndex+1; i<len; i++) {
            int valueTemp = (i-startIndex) * (height[i]<startHeight ? height[i] : startHeight);;
            if(valueTemp > valueMax) {
                valueMax = valueTemp;
            }
        }
        return valueMax;
    }
}
